package com.mlh.dp.old;
/*
题目：
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，
影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。
*/

public class Steal {
    //思路：index作为数组下标，从0开始，这家偷还是不偷来做选择
    //利用暴力递归，可以简单的做出来
    //想这类题目都可以用一个index不断缩小可选择的范围的思路，类似于找钱的题目
    //我这边的算法是从尾到头的  有点不太好看  后面的方法我都改成从头到尾了
    public static int method(int[]houses,int index){
        if(index>=houses.length){
            return 0;
        }
        //index那个房子你偷不偷
        return Math.max(method(houses,index+1),method(houses,index+2)+houses[index]);
    }


    //这边不需要记忆搜索，直接进入表依赖
    public static int method2(int[]houses){
        if(houses.length<=1){
            return houses[0];
        }
        int[]money=new int[houses.length];
        money[0]=houses[0];
        money[1]=Math.max(houses[0],houses[1]);
        for(int i=2;i<money.length;i++){
            money[i]=Math.max(money[i-1],money[i-2]+houses[i]);
        }
        return money[money.length-1];
    }

    //该方法还可以对空间复杂度进行优化
    // 从表依赖可以直接money[i]只会和money[i-1] money[i-2]有关  并不需要保存整个数组
    //以此我们可以设置两个变量来存储这两个值，以此达到优化空间的目的
    public static int method3(int[]houses){
        if(houses.length<=1){
            return houses[0];
        }
        int pre1=0;
        int pre2=0;
        pre1=houses[0];
        pre2=Math.max(houses[0],houses[1]);
        int temp;
        for(int i=2;i<houses.length;i++){
            temp=pre2;
            pre2=Math.max(pre1+houses[i],pre2);
            pre1=temp;
        }

        return pre2;
    }

}
